class Solution {
public:
    /*
    第一个数为正，第二个数为负，第三个数为负，那么这三个数×起来为正
    因此需要两个dp数组，一个存最大值，一个存最小值
    
    */
    double maxProduct(vector<double> arr) {
        vector<double>max_dp(arr.size());
        vector<double>min_dp(arr.size());
        //初始化
        max_dp[0]=arr[0];
        min_dp[0]=arr[0];
        double sum=arr[0];
        for(int i=1;i<arr.size();i++)
        {
            if(arr[i]>0)
            {
                //正*正=正
                //负*正=负
                max_dp[i]=max(arr[i],max_dp[i-1]*arr[i]);
                min_dp[i]=min(arr[i],min_dp[i-1]*arr[i]);
            }else
            {
                //负*负=正
                max_dp[i]=max(arr[i],min_dp[i-1]*arr[i]);
                min_dp[i]=min(arr[i],max_dp[i-1]*arr[i]);
            }
            sum=max(sum,max_dp[i]);
        }
        return sum;
    }
};